#include <stdio.h>
#include<stdlib.h>

void printarray(int row, int col,int *array);
void swaprow(int col, int *array, int a, int b);
void gaussian_elimination(int row,int col, int *array);
int findfreevar(int row, int col, int *array, int *count);
void solve(int row, int col, int *array,int *count, int freevarlen);

int rank_A,rank_B;
int main(int argc, char *argv[])
{
  FILE *fp;//file pointer
  if(argc > 2) {
    printf("Too many argument.\n");
    exit(0);
  }
  if(argc == 1) {//argv[1]
    if((fp = fopen("equation.txt", "r")) != NULL)
    {
    }
    else {
      printf("Can't open equation.txt .\n");
      exit(0);
    }
  }
  else if((fp = fopen(argv[1],"r"))== NULL) {
      printf("Can't open %s\n",argv[1]);
      exit(0);
  }

  int row;
  int col;
  fscanf(fp,"%d",&row);
  fscanf(fp,"%d",&col);
  printf("row:%d  col:%d\n",row,col);
  int *array;
  if(col > row+1) {
    array = (int *)malloc(sizeof(int)*(col-1)*col);
  }
  else {
    array = (int *)malloc(sizeof(int)*row*col);
  }

 // /*Read the profile*/
  int i,j;
  for (i = 0; i < row; ++i) {
    for (j = 0; j < col; ++j) {
      fscanf(fp,"%d",&array[i*col+j]);
    }
  }

  if(fclose(fp) != 0)
    printf("Error in closing file %s\n", argv[1]);
  int is_rA_le_rB;

  int *count = (int *)malloc(sizeof(int)*(col-1));

  gaussian_elimination(row,col,array);
  is_rA_le_rB = findfreevar(row,col,array,count);
  if(is_rA_le_rB) { //rank(A) = rank(B), if is_rA_le_rB==freevarlen
    printf("rank(A)=rank(B),solvable\n");
    solve(row,col,array,count,is_rA_le_rB);
  }
  else { //rank(A) < rank(B), if is_rA_le_rB==0
    printf("rank(A)<rank(B),unsolvable\n");
  }

  /*Release the dynamic array*/
  free(count);
//  free(array);
  return 0;
}

void printarray(int row, int col, int *array)
{
  int i,j;
  printf("-------------------------------------------\n");
  printf(" A:b|");
  for (i = 1; i < col; ++i) {
    printf("%3d |",i);
  }
  printf("|%3d\n",col);
  printf("-------------------------------------------\n");
  for (i = 0; i < row; ++i) {
    printf("%2d: ",i+1);
    for (j = 0; j < col-1; ++j) {
      printf("|%3d ",array[i * col + j]);
    }
      printf("||%3d",array[i * col + j]);
    printf("\n");
    if(i==rank_A-1&&i!=row-1) {
      printf("-------------------------------------------\n");
    }
  }
  printf("-------------------------------------------\n");
}

void swaprow(int col, int *array, int a, int b)
{
  int temp;
  for (int j = 0; j < col; ++j) {
    temp = array[a*col+j];
    array[a*col+j] = array[b*col+j];
    array[b*col+j] = temp;
  }
}

void addrow(int row, int col, int *array, int a, int b)
{                            //row b = row a +row b;
  for (int i = a; i < col; ++i) {
    array[b*col+i] = array[a*col+i] ^ array[b*col+i];
  }
}

void gaussian_elimination(int row,int col, int *array)
{
  int i,j,k;
  i=0;
  for (j = 0; j < col; ++j) {
    if(array[i*col+j]==1) {
label:
      for (k = i+1; k < row; ++k) {
        if(array[k*col+j]==1) {
          addrow(row,col,array,i,k);
        }
      }
      i++;
    }
    else {
      for (k = i+1; k < row; ++k) {
        if(array[k*col+j]==1) {
          swaprow(col,array,k,i);
          goto label;
        }
      }
    }
  }
  /*Has been turned into a line ladder type*/
  for (j = col - 2; j > 0; --j) {
    for (i = j; i > 0; --i) {
      if(array[i*col+j]==1) {
        for (k = i-1; k >=0 ; --k) {
          if(array[k*col+j]==1) {
            addrow(row,col,array,i,k);
          }
        }
      }
    }
  }
  /*Has been made the simplest shape*/
}

int findfreevar(int row, int col, int *array, int *count)
{
  int i,j,k;
  i=0;
  k=0;//k represents the number of free variables
  for (j = 0; j < col-1; ++j) {
    if(array[i*col+j]==1) {
      count[j]=0;
      ++i;
    }
    else {
      count[j]=1;
      ++k;
    }
  }
  rank_A = i;
  j = col - 1;
    if(array[i*col+j]==1) {
      ++i;
    }
  rank_B = i;
  printf("free variable:↓\n");
  printf("-------------------------------------------\n");
  printf("    |");
  for (j = 0; j < col-1; ++j) {
    printf("%3d |",count[j]);
    //printf("%d:%d|",j+1,count[j]);
  }
  printf("\n-------------------------------------------");
  printf("\nrank(A):%d",rank_A);
  printf("\nrank(B):%d\n",rank_B);
  if(rank_A < rank_B) {
    return 0;
  }
  else {
    if(k==0) {
      printf("None free variable, only have special solution.\n");
      printf("    |");
      for (j = 0; j < col-1; ++j) {
        printf("%3d |",array[(j*col)+col-1]);
      }
      printf("\n");
      exit(0);
    }
    return(k);
  }
}

void solve(int row, int col, int *array, int *count,int freevarlen)
{
  int i,j,k,l;
  printf("To solve:\n");
  printf("-------------------------------------------\n");
  int *freevar = (int*)malloc(sizeof(int)*freevarlen);
  j=0;
  for (i = 0; i < col - 1; ++i) {
    if(count[i]==1) {
      freevar[j]=i;
      ++j;
    }
  }
  for (i = 0; i < freevarlen; ++i) {
    printf("freevar[%d]=%d\n",i,freevar[i]+1);
  }
  k = rank_A + freevarlen;
  for (i = rank_A; i <= k; ++i) {
    for (j = 0; j < col - 1; ++j) {
      if(count[j]==1) {
        array[i*col+j]=1;
      }
    }
  }
  k=0;
  for (i = rank_A; i < rank_A+freevarlen; ++i) {
    l=0;
    for (j = 0; j < col-1; ++j) {
      if(array[i*col+j]==0) {
        array[i*col+j]=array[l*col+freevar[k]];
        ++l;
      }
    }
    ++k;
  }
  k=0;
  for (i = rank_A; i < rank_A+freevarlen ; ++i) {
    for (j = 0; j < freevarlen; ++j) {
      if(j!=k) {
        array[i*col+freevar[j]]=0;
      }
    }
    ++k;
  }
  l=0;
  i=rank_A+freevarlen;
  for (j = 0; j < col-1; ++j) {
    if(array[i*col+j]==0) {
      array[i*col+j]=array[l*col+col-1];
      ++l;
    }
  }
  for (j = 0; j < freevarlen; ++j) {
      array[i*col+freevar[j]]=0;
  }
  printarray(col-1,col,array);
  printf("The last row is special solution, the other are base solutions.\n");
  free(freevar);
}
